//1.哈希表（空间复杂度不满足）
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        unordered_set<int> hashset;
        for(auto&e : nums) {
            if(e<=0) continue;
            hashset.insert(e);
        }
        for(int i=1;i<=nums.size();++i) {
            if(!hashset.count(i))
                return i;
        }
        return nums.size()+1;
    }
};
//2.符号标记法
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for(auto&e : nums) {
            if(e<=0 || e>n) e=n+1;        //不满足条件的置为n+1    
        }
        for(int i =0; i < n;++i) {
            int temp = abs(nums[i]);
            if(1<=temp && temp<=n && nums[temp-1]>0)  //已经标记的了不重复标记，比如[1,1]--> [-1,1]
                nums[temp-1] *= -1;
        }
        for(int i =0; i < n;++i) {
            if(nums[i] > 0) 
                return i+1;            
        }
        return n+1;
    }
};

//3.元素置换-----由于每次的交换操作都会使得某一个数交换到正确的位置，因此交换的次数最多为 N，时间复杂度为 O(N)。
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for(int i = 0; i < n; ) {
            if((1 <= nums[i] && nums[i]<=n)  && nums[i] != nums[nums[i]-1]) { //将元素放到它应该在的位置上，如果原来位置上的值相等就不动了
                int temp = nums[nums[i]-1];
                nums[nums[i]-1] = nums[i];
                nums[i] = temp;
            } 
            else
                ++i;
        }
        
        for(int i = 0; i < n; ++i) {
            if(nums[i]<=0) return i+1; //可以省略
            if(nums[i]!=i+1) return i+1;
        }
        return n+1;
    }
};




